from math import log2 as _log2
from ..math.mathematic import e as _e, Pi as _Pi
from ..math.statistics import C as _C

__all__ = [
    "quickSorted",
    "quickSort",
    "bubbleSort",
    "selectionSort",
    "insertionSorting",
    "insertionSort",
    "shellSort",
    "LIS",
    "lenLIS",
    "KMP",
    "Exp",
    "QJS",
    "bezier",
    "bezier_withoutRecursion",
    "FFTComplement",
    "FFT",
    "FFT_withoutRecursion",
]


def quickSorted(arr: list) -> list:
    """快速排序"""
    return (
        len(arr) > 1
        and quickSort(list(filter(lambda x: x <= arr[0], arr[1:])))
        + arr[:1]
        + quickSort(list(filter(lambda x: x > arr[0], arr[1:])))
        or arr
    )


def quickSort(lst: list, l: int, r: int) -> None:
    """快速排序"""
    if l >= r:
        return
    """if r-l+1 < 10:
        insertionSorting(lst, l, r)
        return"""
    """pivot=randint(l,r)
    lst[i], lst[pivot] = lst[pivot], lst[i]"""
    i, j = l, r
    key = lst[i]
    while i < j:
        while i < j and lst[j] >= key:
            j -= 1
        while i < j and lst[i] <= key:
            i += 1
        if i == j:
            lst[i], lst[l] = lst[l], lst[i]
        else:
            lst[i], lst[j] = lst[j], lst[i]
    quickSort(lst, l, j - 1)
    quickSort(lst, i + 1, r)


def bubbleSort(lst: list) -> None:
    """冒泡排序"""
    for i in range(len(lst) - 1):
        change = False
        for j in range(len(lst) - i - 1):
            if lst[j + 1] < lst[j]:
                lst[j + 1], lst[j] = lst[j], lst[j + 1]
                change = True
        if not change:
            return


def selectionSort(lst: list) -> None:
    """选择排序"""
    for i in range(len(lst) - 1):
        mini = i
        for j in range(i + 1, len(lst)):
            if lst[j] < lst[mini]:
                mini = j
        if i != mini:
            lst[i], lst[mini] = lst[mini], lst[i]


def insertionSorting(lst: list, l: int, r: int) -> None:
    """插入排序"""
    for i in range(l, r + 1):
        preIndex = i - 1
        current = lst[i]
        while preIndex >= l and lst[preIndex] > current:
            lst[preIndex + 1] = lst[preIndex]
            preIndex -= 1
        lst[preIndex + 1] = current


def insertionSort(lst: list) -> None:
    """插入排序"""
    for i in range(len(lst)):
        preIndex = i - 1
        current = lst[i]
        while preIndex >= 0 and lst[preIndex] > current:
            lst[preIndex + 1] = lst[preIndex]
            preIndex -= 1
        lst[preIndex + 1] = current


def shellSort(arr: list) -> None:
    """希尔排序"""
    import math

    gap = 1
    while gap < len(arr) / 3:
        gap = gap * 3 + 1
    while gap > 0:
        for i in range(gap, len(arr)):
            temp = arr[i]
            j = i - gap
            while j >= 0 and arr[j] > temp:
                arr[j + gap] = arr[j]
                j -= gap
            arr[j + gap] = temp
        gap = math.floor(gap / 3)


def LIS(lst: list):
    """Longest Increasing Subsequence 最长递增子序列"""
    lens = len(lst)
    l, prev = [1] * lens, [-1] * lens
    for i in range(1, lens):
        for j in range(i):
            if lst[i] > lst[j] and l[i] < l[j] + 1:
                prev[i], l[i] = j, l[j] + 1
    sublen = max(l)
    subend = l.index(sublen)
    sub = [lst[subend]]
    while prev[subend] != -1:
        subend = prev[subend]
        sub.insert(0, lst[subend])
    return sub


def lenLIS(lst: list) -> int:
    """最长递增子序列的长度"""
    lens = len(lst)
    l = [1] * lens
    for i in range(1, lens):
        sub = [l[j] for j in range(i) if lst[i] > lst[j]]
        l[i] = 1 + max(sub, default=0)
    return max(l, default=1)


def KMP(a: str, b: str) -> list:
    """KMP字符串匹配"""
    nex = [-1] * len(a)
    j, o = -1, []
    for i in range(1, len(a)):
        while j >= 0 and a[j + 1] != a[i]:
            j = nex[j]
        j += a[j + 1] == a[i]
        nex[i] = j
    j = -1
    for i in range(len(b)):
        while j >= 0 and a[j + 1] != b[i]:
            j = nex[j]
        j += a[j + 1] == b[i]
        if j == len(a) - 1:
            o.append(i - j)
            j = nex[j]
    return o


def Exp(a: float, b: int) -> float:
    """没卵用的快速幂"""
    ans = 1
    while b != 0:
        if b & 1:
            ans *= a
        b >>= 1
        a **= 2
    return ans


def QJS(lst: list, x: float) -> float:
    """秦久韶算法"""
    o = lst[-1]
    for i in range(len(lst) - 2, -1, -1):
        o = o * x + lst[i]
    return o


def bezier(t: float, lst: list) -> tuple:
    """贝塞尔曲线"""
    if len(lst) == 1:
        return lst[0]
    lst1 = [
        (
            (1 - t) * lst[i][0] + t * lst[i + 1][0],
            (1 - t) * lst[i][1] + t * lst[i + 1][1],
        )
        for i in range(len(lst) - 1)
    ]
    return bezier(t, lst1)


def bezier_withoutRecursion(t: float, lst: list) -> tuple:
    """贝塞尔曲线"""
    n = len(lst) - 1
    x = sum(_C(i, n) * (1 - t) ** (n - i) * t ** i * lst[i][0] for i in range(n + 1))
    y = sum(_C(i, n) * (1 - t) ** (n - i) * t ** i * lst[i][1] for i in range(n + 1))
    return x, y


def FFTComplement(lst: list) -> list:
    """将长度补足为二的幂，以便进行傅里叶变换"""
    leng, count = len(lst), 0
    while leng > 1:
        leng /= 2
        count += 1
    return list(lst) + [0] * (2 ** count - len(lst))


def FFT(lst: list) -> list:
    """Fast Fourier Transform快速傅里叶变换"""
    leng = len(lst)
    if leng == 1:
        return lst
    w = _e ** (2j * _Pi / leng)
    pe = [lst[i] for i in range(leng) if i % 2 == 0]
    po = [lst[i] for i in range(leng) if i % 2 == 1]
    ye, yo = FFT(pe), FFT(po)
    y = [0] * leng
    le = leng // 2
    for i in range(le):
        y[i] = ye[i] + yo[i] * w ** i
        y[i + le] = ye[i] - yo[i] * w ** i
    return y


def FFT_withoutRecursion(lst: list) -> list:
    """快速傅里叶变换无递归实现"""
    leng = len(lst)
    tim = int(_log2(leng))
    l2 = lst
    for i in range(tim):
        le = leng // 2 ** i
        for j in range(2 ** i):
            x1, x2 = j * le, (j + 1) * le
            l2[x1:x2] = [l2[k] for k in range(x1, x2) if not k % 2] + [
                l2[k] for k in range(x1, x2) if k % 2
            ]
    for i in range(tim):
        le = 2 ** i
        w = _e ** (1j * _Pi / le)
        for j in range(le):
            for k in range(leng // 2 // le):
                x1, x2 = 2 * le * k + j, 2 * le * k + le + j
                l2[x1], l2[x2] = l2[x1] + l2[x2] * w ** j, l2[x1] - l2[x2] * w ** j
    return l2
